Immerman-Szelepscényi theorem

Theorem

$\overline{\mathtt{PATH}} \in$ NL

(where $\overline{\mathtt{PATH}}$ language accepts tuple $\langle G,s,t \rangle$ when there is no path from $s$ to $t$ in the graph, i.e. it is the complement of $\mathtt{PATH}$)

Corollary

For every space-constructible $S(n) > \log n$, $\mathbf{NSPACE}(S(n)) = \mathbf{coNSPACE}(S(n))$

(NSPACE)

Notes

• another theorem states that $\mathtt{PATH}$ is $\mathbf{NL}$-complete
• implication is that coNL = NL

References

1. S. Arora, B. Barak. Computational Complexity: A Modern Approach, Cambridge University Press, 2009, pp. 91-92.
2. https://courses.corelab.ntua.gr/pluginfile.php/8936/mod_folder/content/0/CC_Slides_handouts.pdf
3. N. Immerman, “Nondeterministic Space is Closed under Complementation,” SIAM J. Comput., vol. 17, no. 5, pp. 935–938, Oct. 1988, doi: 10.1137/0217058.
4. R. Szelepcsényi, “The method of forced enumeration for nondeterministic automata,” Acta Informatica, vol. 26, no. 3, pp. 279–284, Nov. 1988, doi: 10.1007/BF00299636.